import java.util.HashMap;
import java.util.Map;

public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();
        int[] nums = new int[]{2,-2,2,-4};
        System.out.println(test.subarraysDivByK(nums, 6));
        System.out.println(-7 % 5);
    }

    public int subarraysDivByK1(int[] nums, int k) {
        /**
         * 和可被k整除的子数组
         * 此处的k为分子，即是求 k % x == 0的子数组个数
         * 解法：暴力遍历
         * 结果：超时，未通过案例
         * */
        // 1 预处理
        int n = nums.length;

        // 2 前缀和
        int[] dp = new int[n+1];
        for(int i = 1; i <= n; i++) {
            dp[i] = dp[i-1] + nums[i-1];
        }
//        for(int x: dp) {
//            System.out.print(x + " ");
//        }
//        System.out.println();

        // 3 暴力遍历
        int count = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j < i; j++) {
                int temp = dp[i] - dp[j];
                if(temp % k == 0) {
                    count ++;
                }
            }
        }

        // 4 返回值
        return count;
    }

    public int subarraysDivByK2(int[] nums, int k) {
        /**
         * 和可被k整除的子数组
         * 此处的k为分子，即是求 k % x == 0的子数组个数
         * 解法：动态规划
         * 结果：超时，未通过案例
         * */
        // 1 预处理
        int n = nums.length;

        // 2 前缀和
        int[] arr = new int[n+1];
        for(int i = 1; i <= n; i++) {
            arr[i] = arr[i-1] + nums[i-1];
        }
        int[][] dp = new int[n+1][n+1];
        int count = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = i; j <= n; j++) {
                dp[i][j] = arr[j] - arr[i-1];
                if (dp[i][j] % k == 0) count ++;
            }
        }
        for(int[] x: dp) {
            for(int e: x) {
                System.out.print(e + "\t");
            }
            System.out.println();
        }

        // 3 使用map进行优化查找

        // 4 返回值
        return count;
    }

    public int subarraysDivByK(int[] nums, int k) {
        /**
         * 和可被k整除的子数组
         * 此处的k为分子，即是求 k % x == 0的子数组个数
         * 解法：前缀和
         * 结果：
         * */
        // 1 预处理
        int n = nums.length;

        // 2 前缀和
        int[] dp = new int[n+1];
        for(int i = 1; i <= n; i++) {
            dp[i] = dp[i-1] + nums[i-1];
        }

        // 3 使用map进行优化查找
        int count = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 1; i <= n; i++) {
            // -1 入图维护
            int prevMod = ((dp[i - 1] % k) + k) % k;
            map.put(prevMod, map.getOrDefault(prevMod, 0) + 1);

            // -2 查找
            int curMod = ((dp[i] % k) + k) % k;
            count += map.getOrDefault(curMod, 0);

        }

        // 4 返回值
        return count;
    }
}
